<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Lexicographic code</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Lexicographic_code"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.pygments.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Lexicographic_code rootpage-Lexicographic_code skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Lexicographic code</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p><b>Lexicographic codes</b> or lexicodes are greedily generated <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting codes</a> with remarkably good properties. They were produced independently by
<a href="Vladimir_Levenshtein" title="Vladimir Levenshtein">Vladimir Levenshtein</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> and by <a href="John_Horton_Conway" title="John Horton Conway">John Horton Conway</a> and <a href="Neil_Sloane" title="Neil Sloane">Neil Sloane</a>.<sup id="cite_ref-conslo_2-0" class="reference"><a href="#cite_note-conslo-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> The binary lexicographic codes are <a href="Linear_code" title="Linear code">linear codes</a>, and include the <a href="Hamming_code" title="Hamming code">Hamming codes</a> and the <a href="Binary_Golay_code" title="Binary Golay code">binary Golay codes</a>.<sup id="cite_ref-conslo_2-1" class="reference"><a href="#cite_note-conslo-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="Construction">Construction</h2></div>
<p>A lexicode of length <i>n</i> and minimum distance <i>d</i> over a <a href="Finite_field" title="Finite field">finite field</a> is generated by starting with the all-zero vector and iteratively adding the next vector (in <a href="Lexicographic_order" title="Lexicographic order">lexicographic order</a>) of minimum <a href="Hamming_distance" title="Hamming distance">Hamming distance</a> <i>d</i> from the vectors added so far. As an example, the length-3 lexicode of minimum distance 2 would consist of the vectors marked by an "X" in the following example:
</p>
<dl><dd><table class="wikitable">
<tbody><tr>
<th>Vector
</th>
<th>In code?
</th></tr>
<tr>
<td>000
</td>
<td>X
</td></tr>
<tr>
<td>001
</td>
<td>
</td></tr>
<tr>
<td>010
</td>
<td>
</td></tr>
<tr>
<td>011
</td>
<td>X
</td></tr>
<tr>
<td>100
</td>
<td>
</td></tr>
<tr>
<td>101
</td>
<td>X
</td></tr>
<tr>
<td>110
</td>
<td>X
</td></tr>
<tr>
<td>111
</td>
<td>
</td></tr></tbody></table></dd></dl>
<p>Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2<sup>m</sup> codewords dictionnary.
For example, F<sub>4</sub> code (n=4,d=2,m=3), extended Hamming code (n=8,d=4,m=4) and especially Golay code (n=24,d=8,m=12) shows exceptional compactness compared to neighbors.
</p>
<dl><dd><table class="wikitable">
<tbody><tr>
<th>n \ d
</th>
<th>1
</th>
<th>2
</th>
<th>3
</th>
<th>4
</th>
<th>5
</th>
<th>6
</th>
<th>7
</th>
<th>8
</th>
<th>9
</th>
<th>10
</th>
<th>11
</th>
<th>12
</th>
<th>13
</th>
<th>14
</th>
<th>15
</th>
<th>16
</th>
<th>17
</th>
<th>18
</th></tr>
<tr>
<th>1
</th>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>2
</th>
<td>2
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>3
</th>
<td>3
</td>
<td>2
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>4
</th>
<td>4
</td>
<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">3
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>5
</th>
<td>5
</td>
<td>4
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>6
</th>
<td>6
</td>
<td>5
</td>
<td>3
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>7
</th>
<td>7
</td>
<td>6
</td>
<td>4
</td>
<td>3
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>8
</th>
<td>8
</td>
<td>7
</td>
<td>4
</td>
<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">4
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>9
</th>
<td>9
</td>
<td>8
</td>
<td>5
</td>
<td>4
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>10
</th>
<td>10
</td>
<td>9
</td>
<td>6
</td>
<td>5
</td>
<td>3
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>11
</th>
<td>11
</td>
<td>10
</td>
<td>7
</td>
<td>6
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>12
</th>
<td>12
</td>
<td>11
</td>
<td>8
</td>
<td>7
</td>
<td>4
</td>
<td>4
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>13
</th>
<td>13
</td>
<td>12
</td>
<td>9
</td>
<td>8
</td>
<td>5
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>14
</th>
<td>14
</td>
<td>13
</td>
<td>10
</td>
<td>9
</td>
<td>6
</td>
<td>5
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>15
</th>
<td>15
</td>
<td>14
</td>
<td>11
</td>
<td>10
</td>
<td>7
</td>
<td>6
</td>
<td>5
</td>
<td>4
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>16
</th>
<td>16
</td>
<td>15
</td>
<td>11
</td>
<td>11
</td>
<td>8
</td>
<td>7
</td>
<td>5
</td>
<td>5
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>17
</th>
<td>17
</td>
<td>16
</td>
<td>12
</td>
<td>11
</td>
<td>9
</td>
<td>8
</td>
<td>6
</td>
<td>5
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>
</td></tr>
<tr>
<th>18
</th>
<td>18
</td>
<td>17
</td>
<td>13
</td>
<td>12
</td>
<td>9
</td>
<td>9
</td>
<td>7
</td>
<td>6
</td>
<td>3
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>19
</th>
<td>19
</td>
<td>18
</td>
<td>14
</td>
<td>13
</td>
<td>10
</td>
<td>9
</td>
<td>8
</td>
<td>7
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>20
</th>
<td>20
</td>
<td>19
</td>
<td>15
</td>
<td>14
</td>
<td>11
</td>
<td>10
</td>
<td>9
</td>
<td>8
</td>
<td>5
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>21
</th>
<td>21
</td>
<td>20
</td>
<td>16
</td>
<td>15
</td>
<td>12
</td>
<td>11
</td>
<td>10
</td>
<td>9
</td>
<td>5
</td>
<td>5
</td>
<td>3
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>22
</th>
<td>22
</td>
<td>21
</td>
<td>17
</td>
<td>16
</td>
<td>12
</td>
<td>12
</td>
<td>11
</td>
<td>10
</td>
<td>6
</td>
<td>5
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>23
</th>
<td>23
</td>
<td>22
</td>
<td>18
</td>
<td>17
</td>
<td>13
</td>
<td>12
</td>
<td>12
</td>
<td>11
</td>
<td>6
</td>
<td>6
</td>
<td>5
</td>
<td>4
</td>
<td>2
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>24
</th>
<td>24
</td>
<td>23
</td>
<td>19
</td>
<td>18
</td>
<td>14
</td>
<td>13
</td>
<td>12
</td>
<td style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">12
</td>
<td>7
</td>
<td>6
</td>
<td>5
</td>
<td>5
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>25
</th>
<td>25
</td>
<td>24
</td>
<td>20
</td>
<td>19
</td>
<td>15
</td>
<td>14
</td>
<td>12
</td>
<td>12
</td>
<td>8
</td>
<td>7
</td>
<td>6
</td>
<td>5
</td>
<td>3
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td>
<td>1
</td></tr>
<tr>
<th>26
</th>
<td>26
</td>
<td>25
</td>
<td>21
</td>
<td>20
</td>
<td>16
</td>
<td>15
</td>
<td>12
</td>
<td>12
</td>
<td>9
</td>
<td>8
</td>
<td>7
</td>
<td>6
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>2
</td>
<td>1
</td></tr>
<tr>
<th>27
</th>
<td>27
</td>
<td>26
</td>
<td>22
</td>
<td>21
</td>
<td>17
</td>
<td>16
</td>
<td>13
</td>
<td>12
</td>
<td>9
</td>
<td>9
</td>
<td>7
</td>
<td>7
</td>
<td>5
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td>
<td>2
</td></tr>
<tr>
<th>28
</th>
<td>28
</td>
<td>27
</td>
<td>23
</td>
<td>22
</td>
<td>18
</td>
<td>17
</td>
<td>13
</td>
<td>13
</td>
<td>10
</td>
<td>9
</td>
<td>8
</td>
<td>7
</td>
<td>5
</td>
<td>5
</td>
<td>3
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td></tr>
<tr>
<th>29
</th>
<td>29
</td>
<td>28
</td>
<td>24
</td>
<td>23
</td>
<td>19
</td>
<td>18
</td>
<td>14
</td>
<td>13
</td>
<td>11
</td>
<td>10
</td>
<td>8
</td>
<td>8
</td>
<td>6
</td>
<td>5
</td>
<td>4
</td>
<td>3
</td>
<td>2
</td>
<td>2
</td></tr>
<tr>
<th>30
</th>
<td>30
</td>
<td>29
</td>
<td>25
</td>
<td>24
</td>
<td>19
</td>
<td>19
</td>
<td>15
</td>
<td>14
</td>
<td>12
</td>
<td>11
</td>
<td>9
</td>
<td>8
</td>
<td>6
</td>
<td>6
</td>
<td>5
</td>
<td>4
</td>
<td>2
</td>
<td>2
</td></tr>
<tr>
<th>31
</th>
<td>31
</td>
<td>30
</td>
<td>26
</td>
<td>25
</td>
<td>20
</td>
<td>19
</td>
<td>16
</td>
<td>15
</td>
<td>12
</td>
<td>12
</td>
<td>10
</td>
<td>9
</td>
<td>6
</td>
<td>6
</td>
<td>6
</td>
<td>5
</td>
<td>3
</td>
<td>2
</td></tr>
<tr>
<th>32
</th>
<td>32
</td>
<td>31
</td>
<td>26
</td>
<td>26
</td>
<td>21
</td>
<td>20
</td>
<td>16
</td>
<td>16
</td>
<td>13
</td>
<td>12
</td>
<td>11
</td>
<td>10
</td>
<td>7
</td>
<td>6
</td>
<td>6
</td>
<td>6
</td>
<td>3
</td>
<td>3
</td></tr>
<tr>
<th>33
</th>
<td>...
</td>
<td>32
</td>
<td>...
</td>
<td>26
</td>
<td>...
</td>
<td>21
</td>
<td>...
</td>
<td>16
</td>
<td>...
</td>
<td>13
</td>
<td>...
</td>
<td>11
</td>
<td>...
</td>
<td>7
</td>
<td>...
</td>
<td>6
</td>
<td>...
</td>
<td>3
</td></tr></tbody></table></dd></dl>
<p>All odd d-bit lexicode distances are exact copies of the even d+1 bit distances minus the last dimension, so
an odd-dimensional space can never create something new or more interesting than the d+1 even-dimensional space above.
</p><p>Since lexicodes are linear, they can also be constructed by means of their <a href="Basis_(linear_algebra)" title="Basis (linear algebra)"> basis</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2></div>
<p>Following C generate lexicographic code and parameters are set for the Golay code (N=24, D=8).
</p>
<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre><span class="cp">#include</span><span class="w"> </span><span class="cpf"><stdio.h></span>
<span class="cp">#include</span><span class="w"> </span><span class="cpf"><stdlib.h></span>
<span class="kt">int</span><span class="w"> </span><span class="nf">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="cm">/* GOLAY CODE generation */</span>
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">j</span><span class="p">,</span><span class="w"> </span><span class="n">k</span><span class="p">;</span><span class="w"> </span>
<span class="w"> </span>
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">_pc</span><span class="p">[</span><span class="mi">1</span><span class="o"><<</span><span class="mi">16</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">{</span><span class="mi">0</span><span class="p">};</span><span class="w"> </span><span class="c1">// PopCount Macro</span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="o"><<</span><span class="mi">16</span><span class="p">);</span><span class="w"> </span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="w"> </span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">j</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="mi">16</span><span class="p">;</span><span class="w"> </span><span class="n">j</span><span class="o">++</span><span class="p">)</span><span class="w"> </span>
<span class="w"> </span><span class="n">_pc</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="o">>></span><span class="n">j</span><span class="p">)</span><span class="o">&</span><span class="mi">1</span><span class="p">;</span>
<span class="cp">#define pc(X) (_pc[(X)&0xffff] + _pc[((X)>>16)&0xffff])</span>
<span class="w"> </span>
<span class="cp">#define N 24 </span><span class="c1">// N bits</span>
<span class="cp">#define D 8 </span><span class="c1">// D bits distance</span>
<span class="w"> </span><span class="kt">unsigned</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">malloc</span><span class="p">(</span><span class="mi">1</span><span class="o"><<</span><span class="mi">29</span><span class="p">);</span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="o"><<</span><span class="n">N</span><span class="p">);</span><span class="w"> </span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="w"> </span>
<span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="c1">// Scan all previous</span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">k</span><span class="o">=</span><span class="n">j</span><span class="mi">-1</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">>=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">--</span><span class="p">)</span><span class="w"> </span><span class="c1">// lexicodes.</span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">pc</span><span class="p">(</span><span class="n">z</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">^</span><span class="n">i</span><span class="p">)</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">D</span><span class="p">)</span><span class="w"> </span><span class="c1">// Reverse checking</span>
<span class="w"> </span><span class="k">break</span><span class="p">;</span><span class="w"> </span><span class="c1">// is way faster...</span>
<span class="w"> </span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">k</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">-1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="c1">// Add new lexicode</span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o"><</span><span class="w"> </span><span class="n">N</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">++</span><span class="p">)</span><span class="w"> </span><span class="c1">// & print it</span>
<span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="o">>></span><span class="n">k</span><span class="p">)</span><span class="o">&</span><span class="mi">1</span><span class="p">);</span><span class="w"> </span>
<span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">" : %d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span><span class="w"> </span><span class="n">j</span><span class="p">);</span><span class="w"> </span>
<span class="w"> </span><span class="n">z</span><span class="p">[</span><span class="n">j</span><span class="o">++</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">i</span><span class="p">;</span><span class="w"> </span>
<span class="w"> </span><span class="p">}</span><span class="w"> </span>
<span class="w"> </span><span class="p">}</span><span class="w"> </span>
<span class="p">}</span>
</pre></div>
<div class="mw-heading mw-heading2"><h2 id="Combinatorial_game_theory">Combinatorial game theory</h2></div>
<p>The theory of lexicographic codes is closely connected to <a href="Combinatorial_game_theory" title="Combinatorial game theory">combinatorial game theory</a>. In particular, the codewords in a binary lexicographic code of distance <i>d</i> encode the winning positions in a variant of <a href="Grundy's_game" title="Grundy's game">Grundy's game</a>, played on a collection of heaps of stones, in which each move consists of replacing any one heap by at most <i>d</i> − 1 smaller heaps, and the goal is to take the last stone.<sup id="cite_ref-conslo_2-2" class="reference"><a href="#cite_note-conslo-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFLevenšteĭn1960" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Vladimir_Levenshtein" title="Vladimir Levenshtein">Levenšteĭn, V. I.</a> (1960), <a rel="nofollow" class="external text" href="https://mi.mathnet.ru/dan39976">"Об одном классе систематических кодов"</a> [A class of systematic codes], <i><a href="Proceedings_of_the_USSR_Academy_of_Sciences" title="Proceedings of the USSR Academy of Sciences">Doklady Akademii Nauk SSSR</a></i> (in Russian), <b>131</b> (5): <span class="nowrap">1011–</span>1014, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0122629">0122629</a></cite>; English translation in <i>Soviet Math. Doklady</i> 1 (1960), 368–371</span>
</li>
<li id="cite_note-conslo-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-conslo_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-conslo_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-conslo_2-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFConwaySloane1986" class="citation cs2"><a href="John_Horton_Conway" title="John Horton Conway">Conway, John H.</a>; <a href="Neil_Sloane" title="Neil Sloane">Sloane, N. J. A.</a> (1986), "Lexicographic codes: error-correcting codes from game theory", <i><a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a></i>, <b>32</b> (3): <span class="nowrap">337–</span>348, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.392.795">10.1.1.392.795</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1986.1057187">10.1109/TIT.1986.1057187</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0838197">0838197</a></cite></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFTrachtenberg2002" class="citation cs2">Trachtenberg, Ari (2002), "Designing lexicographic codes with a given trellis complexity", <i><a href="IEEE_Transactions_on_Information_Theory" title="IEEE Transactions on Information Theory">IEEE Transactions on Information Theory</a></i>, <b>48</b> (1): <span class="nowrap">89–</span>100, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F18.971740">10.1109/18.971740</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1866958">1866958</a></cite></span>
</li>
</ol></div>
<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>
<ul><li><a rel="nofollow" class="external text" href="http://burtleburtle.net/bob/math/lexicode.html">Bob Jenkins table of binary lexicodes</a></li>
<li><a rel="nofollow" class="external text" href="http://ipsit.bu.edu/comp.html">On-line generator for lexicodes and their variants</a></li>
<li><abbr title="On-Line Encyclopedia of Integer Sequences">OEIS</abbr> <a rel="nofollow" class="external text" href="https://oeis.org/A075928">sequence A075928 (List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers.)</a></li>
<li><a rel="nofollow" class="external text" href="http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html">Error-Correcting Codes on Graphs: Lexicodes</a>, <a rel="nofollow" class="external text" href="http://oeis.org/search?q=Trellises">Trellises and Factor Graphs</a></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2024-01-11" href="https://en.wikipedia.org/wiki/?title=Lexicographic_code&oldid=1195022069">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>